#include <inc/string.h>
#include <inc/partition.h>

#include "fs.h"

// --------------------------------------------------------------
// Super block
// --------------------------------------------------------------

// Validate the file system super-block.
void
check_super(void) {
    if (super->s_magic != FS_MAGIC)
        panic("bad file system magic number");

    if (super->s_nblocks > DISKSIZE / BLKSIZE)
        panic("file system is too large");

    cprintf("superblock is good\n");
}

// --------------------------------------------------------------
// Free block bitmap
// --------------------------------------------------------------

// Check to see if the block bitmap indicates that block 'blockno' is free.
// Return 1 if the block is free, 0 if not.
bool
block_is_free(uint32_t blockno) {
    if (super == 0 || blockno >= super->s_nblocks)
        return 0;
    if (bitmap[blockno / 32] & (1 << (blockno % 32)))
        return 1;
    return 0;
}

// Mark a block free in the bitmap
void
free_block(uint32_t blockno) {
    // Blockno zero is the null pointer of block numbers.
    if (blockno == 0)
        panic("attempt to free zero block");
    bitmap[blockno / 32] |= 1 << (blockno % 32);
}

// Search the bitmap for a free block and allocate it.  When you
// allocate a block, immediately flush the changed bitmap block
// to disk.
//
// 在位图中搜索一个空闲块并分配它。 当你分配一个块时，立即改变对应块的bit位并刷新到磁盘。
// (我们可以算一下：硬盘3GB,一共有 3GB/4KB = 786,432个块，而bitmap 4KB*8=32KB，由于是无符号整型，可以表示32KB*32=1,048,576个块,足够表示了)
//
// Return block number allocated on success,
// -E_NO_DISK if we are out of blocks.
//
// Hint: use free_block as an example for manipulating the bitmap.
int
alloc_block(void) {
    // The bitmap consists of one or more blocks.  A single bitmap block
    // contains the in-use bits for BLKBITSIZE blocks.  There are
    // super->s_nblocks blocks in the disk altogether.
    // 位图由一个或多个块组成。 一个位图块包含BLKBITSIZE块的使用中的位。 在磁盘中总共有super->s_nblocks块。

    // LAB 5: Your code here.
    /**
     * 相当于整个磁盘遍历了,查询哪个块是空的. 这里其实可以使用二分进行优化
     */
    uint32_t blockno = 1;
    for (; blockno < super->s_nblocks; ++blockno) {
        if (!block_is_free(blockno)) continue;
        bitmap[blockno / 32] &= ~(1 << (blockno % 32));
        flush_block(diskaddr(blockno));
        return blockno;
    }
    return -E_NO_DISK;
}

// Validate the file system bitmap.
//
// Check that all reserved blocks -- 0, 1, and the bitmap blocks themselves --
// are all marked as in-use.
void
check_bitmap(void) {
    uint32_t i;

    // Make sure all bitmap blocks are marked in-use
    for (i = 0; i * BLKBITSIZE < super->s_nblocks; i++)
        assert(!block_is_free(2 + i));

    // Make sure the reserved and root blocks are marked in-use.
    assert(!block_is_free(0));
    assert(!block_is_free(1));

    cprintf("bitmap is good\n");
}

// --------------------------------------------------------------
// File system structures
// --------------------------------------------------------------



// Initialize the file system
void
fs_init(void) {
    static_assert(sizeof(struct File) == 256);

    // Find a JOS disk.  Use the second IDE disk (number 1) if available
    if (ide_probe_disk1())
        ide_set_disk(1);
    else
        ide_set_disk(0);
    bc_init();
    // Set "super" to point to the super block.
    super = diskaddr(1);
    check_super();

    // Set "bitmap" to the beginning of the first bitmap block.
    bitmap = diskaddr(2);
    check_bitmap();

}

// Find the disk block number slot for the 'filebno'th block in file 'f'.
// Set '*ppdiskbno' to point to that slot.
// The slot will be one of the f->f_direct[] entries,
// or an entry in the indirect block.
// When 'alloc' is set, this function will allocate an indirect block if necessary.
//
// Returns:
//	0 on success (but note that *ppdiskbno might equal 0).
//	-E_NOT_FOUND if the function needed to allocate an indirect block, but
//		alloc was 0.
//	-E_NO_DISK if there's no space on the disk for an indirect block.
//	-E_INVAL if filebno is out of range (it's >= NDIRECT + NINDIRECT).
//
// Analogy: This is like pgdir_walk for files.
// Hint: Don't forget to clear any block you allocate.

static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc) {
    // LAB 5: Your code here.
    if (filebno >= NDIRECT + NINDIRECT)  return -E_INVAL;

    if (filebno < NDIRECT) {
        *ppdiskbno = f->f_direct + filebno;
    } else {
        uint32_t blockno;
        if (f->f_indirect == 0) {
            if (alloc == false)  return -E_NOT_FOUND;
            if ((blockno = alloc_block()) < 0) {
                return -E_NO_DISK;
            }
            f->f_indirect = blockno;
            memset(diskaddr(blockno), 0, BLKSIZE); //防止此地址有数据残留
            flush_block(diskaddr(blockno));
        }
        filebno -= NDIRECT;
        if (ppdiskbno != NULL) {
            *ppdiskbno = (uint32_t *) diskaddr(f->f_indirect) + filebno;
        }
    }
    return 0;
}

// Set *blk to the address in memory where the filebno'th
// block of file 'f' would be mapped.
//
// Returns 0 on success, < 0 on error.  Errors are:
//	-E_NO_DISK if a block needed to be allocated but the disk is full.
//	-E_INVAL if filebno is out of range.
//
// Hint: Use file_block_walk and alloc_block.
int
file_get_block(struct File *f, uint32_t filebno, char **blk) {
    // LAB 5: Your code here.
    uint32_t *blkno;
    int ret;
    if (0 > (ret = file_block_walk(f, filebno, &blkno, 1))) {
        return ret;
    }
    if (*blkno == 0) { // 不能获取到超级块的，只能分配个新的块
        if (0 > (*blkno = alloc_block())) return -E_NO_DISK;
        memset(diskaddr(*blkno), 0, BLKSIZE);
        flush_block(diskaddr(*blkno));
    }
    *blk = diskaddr(*blkno);
    return 0;
}

// Try to find a file named "name" in dir.  If so, set *file to it.
//
// Returns 0 and sets *file on success, < 0 on error.  Errors are:
//	-E_NOT_FOUND if the file is not found
static int
dir_lookup(struct File *dir, const char *name, struct File **file) {
    int r;
    uint32_t i, j, nblock;
    char *blk;
    struct File *f;

    // Search dir for name.
    // We maintain the invariant that the size of a directory-file
    // is always a multiple of the file system's block size.
    assert((dir->f_size % BLKSIZE) == 0);
    nblock = dir->f_size / BLKSIZE;
    for (i = 0; i < nblock; i++) {
        if ((r = file_get_block(dir, i, &blk)) < 0)
            return r;
        f = (struct File *) blk;
        for (j = 0; j < BLKFILES; j++)
            if (strcmp(f[j].f_name, name) == 0) {
                *file = &f[j];
                return 0;
            }
    }
    return -E_NOT_FOUND;
}

// Set *file to point at a free File structure in dir.  The caller is
// responsible for filling in the File fields.
static int
dir_alloc_file(struct File *dir, struct File **file) {
    int r;
    uint32_t nblock, i, j;
    char *blk;
    struct File *f;

    assert((dir->f_size % BLKSIZE) == 0);
    nblock = dir->f_size / BLKSIZE;
    for (i = 0; i < nblock; i++) {
        if ((r = file_get_block(dir, i, &blk)) < 0)
            return r;
        f = (struct File *) blk;
        for (j = 0; j < BLKFILES; j++)
            if (f[j].f_name[0] == '\0') {
                *file = &f[j];
                return 0;
            }
    }
    dir->f_size += BLKSIZE;
    if ((r = file_get_block(dir, i, &blk)) < 0)
        return r;
    f = (struct File *) blk;
    *file = &f[0];
    return 0;
}

// Skip over slashes.
static const char *
skip_slash(const char *p) {
    while (*p == '/')
        p++;
    return p;
}

// Evaluate a path name, starting at the root.
// On success, set *pf to the file we found
// and set *pdir to the directory the file is in.
// If we cannot find the file but find the directory
// it should be in, set *pdir and copy the final path
// element into lastelem.
static int
walk_path(const char *path, struct File **pdir, struct File **pf, char *lastelem) {
    const char *p;
    char name[MAXNAMELEN];
    struct File *dir, *f;
    int r;

    // if (*path != '/')
    //	return -E_BAD_PATH;
    path = skip_slash(path);
    f = &super->s_root;
    dir = 0;
    name[0] = 0;

    if (pdir)
        *pdir = 0;
    *pf = 0;
    while (*path != '\0') {
        dir = f;
        p = path;
        while (*path != '/' && *path != '\0')
            path++;
        if (path - p >= MAXNAMELEN)
            return -E_BAD_PATH;
        memmove(name, p, path - p);
        name[path - p] = '\0';
        path = skip_slash(path);

        if (dir->f_type != FTYPE_DIR)
            return -E_NOT_FOUND;

        if ((r = dir_lookup(dir, name, &f)) < 0) {
            if (r == -E_NOT_FOUND && *path == '\0') {
                if (pdir)
                    *pdir = dir;
                if (lastelem)
                    strcpy(lastelem, name);
                *pf = 0;
            }
            return r;
        }
    }

    if (pdir)
        *pdir = dir;
    *pf = f;
    return 0;
}

// --------------------------------------------------------------
// File operations
// --------------------------------------------------------------

// Create "path".  On success set *pf to point at the file and return 0.
// On error return < 0.
int
file_create(const char *path, struct File **pf) {
    char name[MAXNAMELEN];
    int r;
    struct File *dir, *f;

    if ((r = walk_path(path, &dir, &f, name)) == 0)
        return -E_FILE_EXISTS;
    if (r != -E_NOT_FOUND || dir == 0)
        return r;
    if ((r = dir_alloc_file(dir, &f)) < 0)
        return r;

    strcpy(f->f_name, name);
    *pf = f;
    file_flush(dir);
    return 0;
}

// Open "path".  On success set *pf to point at the file and return 0.
// On error return < 0.
int
file_open(const char *path, struct File **pf) {
    return walk_path(path, 0, pf, 0);
}

// Read count bytes from f into buf, starting from seek position
// offset.  This meant to mimic the standard pread function.
// 从f的寻址位置偏移开始，读取count字节到 buf 中。
// 这意味着要仿造标准的pread函数。
//
// Returns the number of bytes read, < 0 on error.
ssize_t
file_read(struct File *f, void *buf, size_t count, off_t offset) {
    int r, bn;
    off_t pos;
    char *blk;

    if (offset >= f->f_size)
        return 0;

    count = MIN(count, f->f_size - offset);

    for (pos = offset; pos < offset + count;) {
        if ((r = file_get_block(f, pos / BLKSIZE, &blk)) < 0)
            return r;
        /**
         * BLKSIZE - (pos % BLKSIZE) 表示：移动到下一个块起始点所需的偏移量
         * offset + count - pos 表示：pos距文件最后字节的偏移量
         * 为什么取MIN，很明显：如果pos已经是在此文件最后一个块中，那么能读取的字节不足一个块了，所以就不能将它偏移到下一个块当中，将其取小值
         */
        bn = MIN(BLKSIZE - (pos % BLKSIZE), offset + count - pos);
        memmove(buf, blk + (pos % BLKSIZE), bn); //blk + (pos % BLKSIZE) 块内偏移量
        pos += bn;
        buf += bn;
    }

    return count;
}


// Write count bytes from buf into f, starting at seek position
// offset.  This is meant to mimic the standard pwrite function.
// Extends the file if necessary.
// Returns the number of bytes written, < 0 on error.
int
file_write(struct File *f, const void *buf, size_t count, off_t offset) {
    int r, bn;
    off_t pos;
    char *blk;

    // Extend file if necessary
    if (offset + count > f->f_size)
        if ((r = file_set_size(f, offset + count)) < 0)
            return r;

    for (pos = offset; pos < offset + count;) {
        if ((r = file_get_block(f, pos / BLKSIZE, &blk)) < 0)
            return r;
        bn = MIN(BLKSIZE - pos % BLKSIZE, offset + count - pos);
        memmove(blk + pos % BLKSIZE, buf, bn);
        pos += bn;
        buf += bn;
    }

    return count;
}

// Remove a block from file f.  If it's not there, just silently succeed.
// Returns 0 on success, < 0 on error.
static int
file_free_block(struct File *f, uint32_t filebno) {
    int r;
    uint32_t *ptr;

    if ((r = file_block_walk(f, filebno, &ptr, 0)) < 0)
        return r;
    if (*ptr) {
        free_block(*ptr);
        *ptr = 0;
    }
    return 0;
}

// Remove any blocks currently used by file 'f',
// but not necessary for a file of size 'newsize'.
// For both the old and new sizes, figure out the number of blocks required,
// and then clear the blocks from new_nblocks to old_nblocks.
// If the new_nblocks is no more than NDIRECT, and the indirect block has
// been allocated (f->f_indirect != 0), then free the indirect block too.
// (Remember to clear the f->f_indirect pointer so you'll know
// whether it's valid!)
// Do not change f->f_size.
static void
file_truncate_blocks(struct File *f, off_t newsize) {
    int r;
    uint32_t bno, old_nblocks, new_nblocks;

    old_nblocks = (f->f_size + BLKSIZE - 1) / BLKSIZE;
    new_nblocks = (newsize + BLKSIZE - 1) / BLKSIZE;
    for (bno = new_nblocks; bno < old_nblocks; bno++)
        if ((r = file_free_block(f, bno)) < 0)
            cprintf("warning: file_free_block: %e", r);

    if (new_nblocks <= NDIRECT && f->f_indirect) {
        free_block(f->f_indirect);
        f->f_indirect = 0;
    }
}

// Set the size of file f, truncating or extending as necessary.
int
file_set_size(struct File *f, off_t newsize) {
    if (f->f_size > newsize)
        file_truncate_blocks(f, newsize);
    f->f_size = newsize;
    flush_block(f);
    return 0;
}

// Flush the contents and metadata of file f out to disk.
// Loop over all the blocks in file.
// Translate the file block number into a disk block number
// and then check whether that disk block is dirty.  If so, write it out.
void
file_flush(struct File *f) {
    int i;
    uint32_t *pdiskbno;

    for (i = 0; i < (f->f_size + BLKSIZE - 1) / BLKSIZE; i++) {
        if (file_block_walk(f, i, &pdiskbno, 0) < 0 ||
            pdiskbno == NULL || *pdiskbno == 0)
            continue;
        flush_block(diskaddr(*pdiskbno));
    }
    flush_block(f);
    if (f->f_indirect)
        flush_block(diskaddr(f->f_indirect));
}


// Sync the entire file system.  A big hammer.
void
fs_sync(void) {
    int i;
    for (i = 1; i < super->s_nblocks; i++)
        flush_block(diskaddr(i));
}

